const t1 = new Date(); // 开始时间记录
const devide_Xin = function (array, start, end) {
  if (start >= end) return array;
  var baseIndex = Math.floor((start + end) / 2), // 基数索引 取中间
    i = start,
    j = end;
  while (i <= j) {
    while (array[i] < array[baseIndex]) {
      i++;
    }
    while (array[j] > array[baseIndex]) {
      j--;
    }
    if (i <= j) {
      var temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++;
      j--;
    }
  }
  return i;
}
const quickSort_Xin = function (array, start, end) {
  if (array.length < 1) {
    return array;
  }
  const index = devide_Xin(array, start, end);
  if (start < index - 1) {
    quickSort_Xin(array, start, index - 1);
  }
  if (end > index) {
    quickSort_Xin(array, index, end);
  }
  return array;
}

const { randomArr } = require('../createArr')
const result = quickSort_Xin(randomArr, 0, randomArr.length - 1)
const t2 = new Date(); // 结束时间记录
console.log('用时' + (t2 - t1) + '毫秒' + '\n', result)

// ** 优化点:
// 1、用下标取基数，只有一个赋值操作，更快；
// 2、原地交换，不需要新建多余的数组容器存储被划分的数据，节省存

// 不稳定排序